package compiler.scanner.dfa;

import compiler.scanner.nfa.ETransition;
import compiler.scanner.nfa.NFAState;
import compiler.scanner.nfa.NFATransition;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
import java.util.Set;

public class DFAGen
{
    //~ Instance fields --------------------------------------------------------

    private DFAState minimizedDfa;
    private DFAState normalDfa;
    private NFAState nfaStart;

    //~ Constructors -----------------------------------------------------------

    public DFAGen(NFAState start)
    {
        this.nfaStart = start;
        computeDFA();
    }

    //~ Methods ----------------------------------------------------------------

    public DFAState getMinimizedDfa()
    {
        return minimizedDfa;
    }

    public DFAState getNormalDfa()
    {
        return normalDfa;
    }

    private void computeDFA()
    {
        Queue<DFAState>              remaining = new LinkedList<DFAState>();
        Map<Set<NFAState>, DFAState> dfaStates = new HashMap<Set<NFAState>, DFAState>();

        Set<NFAState>                allNfaStates = nfaStart.getReachable();

        // make sure the start is the first one to be processed
        allNfaStates.remove(nfaStart);

        DFAState start = new DFAState(nfaStart.getEClosureStates());
        dfaStates.put(start.subStates, start);
        remaining.offer(start);

        for (NFAState nfaState : allNfaStates)
        {
            DFAState dfaState = new DFAState(nfaState.getEClosureStates());
            dfaStates.put(dfaState.subStates, dfaState);
            remaining.offer(dfaState);
        }

        while (remaining.size() > 0)
        {
            DFAState       dfaState = remaining.remove();
            Set<Character> allChars = new HashSet<Character>();

            for (NFAState nfaState : (Set<NFAState>)dfaState.subStates)
            {
                for (NFATransition trans : nfaState.getTransitions())
                {
                    if (!(trans instanceof ETransition))
                    {
                        allChars.add(trans.getCharacter());
                    }
                }
            }

            for (Character c : allChars)
            {
                Set<NFAState> newStateKernel = dfaState.getAllTransitionsOn(c);

                if (dfaStates.containsKey(newStateKernel))
                {
                    dfaState.transitions.put(c, dfaStates.get(newStateKernel));
                }
                else
                {
                    DFAState newState = new DFAState(newStateKernel);
                    dfaState.transitions.put(c, newState);
                    dfaStates.put(newStateKernel, newState);
                    remaining.offer(newState);
                }
            }
        }

        normalDfa    = start;

        minimizedDfa = new DFAMinimizer(new HashSet<DFAState>(dfaStates.values()), start).getMinimizedDFA();
    }
}
